/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        509.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 12:54
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 斐波那契数
 */
#include <vector>

using namespace std;

class Solution {
public:
//    int fib(int n) {
//        if (n < 1)
//            return 0;
//        if (n == 1 || n == 2) {
//            return 1;
//        }
//        vector<int> dp(n + 1, 0);
//        dp[1] = dp[2] = 1;
//        for (int i = 3; i <= n; ++i) {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//    }

    int fib(int n) {
        if (n < 1)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; ++i) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
};
